
\subsection{Problem 1 (8)}

Recommended, 8 Points: As a first step, implement a test driver, which calls the chosen benchmark with different input data. Compile the test driver (using -Os), and measure the execution time. Next, add loop bounds and other flow facts to the selected benchmark, and analyze the WCET using aiT.
\\
\\
\textbf{Solution:}
\\
\\
\begin{figure}[!htbp]
	\centering
		\includegraphics[width=0.40\textwidth]{figures/ConvexHulls.png}
	\caption{Illustration of the convex hull algorithm (pic from \textit{wiki})}
	\label{fig:convexhull}
\end{figure}
\\
We decided to choose an algorithm which constructs the convex hull of a set of N 2-dimensional points. The source code of the original algorithm can be found in section ~\ref{sec:original}. We did some minor modifications to the original code, like changing some function parameters or putting our set of points in an \textit{point\_t P[N]} array of N points for easy debugging. One can find our source code in section~\ref{sec:v1_source}. To start a new computation, we have to call the function \textit{convex\_hull()} with our presorted (according to the x-coordinate) set of N points. If two points have the same x-coordinates then the points must be sorted by increasing y-coordinates. 
\\
\\
\textit{convex\_hull()} instantly enters the first for-loop and starts with the first 2 nodes from the given set and tests if the next node of the set lies right of or beneath a virtual line drawn through the previous two points. If the next node lies beneath our virtual line (so we would have to make a clockwise turn), we add this next node to the convex hull and remove the current one from it. Otherwise, if the next node lies above our virtual line (so we would now have to make a counter-clockwise turn), the current node remains in the convex hull. We repeat those steps until the last node of the set has been reached, so we've finally constructed the lower hull. Then we go into the second for loop and start from the end of the set and go back to the start of the set with the same steps as before, now constructing the upper hull.
\\
\\
We software-measured an execution time of 5939 cycles. For the analysis with \textit{aiT} we added 4 loop bounds for our 2 for and while loops, as you can see in our \textit{.ais-file} in Section~\ref{sec:ais_v1}. As it can be seen in Figure~\ref{fig:v1_ait}, \textit{aiT} then computed a WCET of 57788 cycles.

\begin{figure}[!htbp]
	\centering
		\includegraphics[width=0.50\textwidth]{figures/v1_ait.png}
	\caption{aiT analysis v1}
	\label{fig:v1_ait}
\end{figure}